/**
 * Copyright 2008 Matthew Purland (m.purland@gmail.com)
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */
package org.variance.version.diff;

import java.nio.ByteBuffer;

/**
 * LCS helper utility.
 *
 * @author Matthew Purland
 */
public class LCS {
	
	/**
	 * Compute the LCS for two byte arrays.
	 * 
	 * Implementation from http://www.cs.princeton.edu/introcs/96optimization/LCS.java.html
	 * 
	 * @param source
	 * @param current
	 * @return
	 */
	public static byte[] computeLCS(byte[] source, byte[] current) {
		int M = source.length;
        int N = current.length;

        // opt[i][j] = length of LCS of x[i..M] and current[j..N]
        int[][] opt = new int[M+1][N+1];

        // compute length of LCS and all subproblems via dynamic programming
        for (int i = M-1; i >= 0; i--) {
            for (int j = N-1; j >= 0; j--) {
                if (source[i] == current[j])
                    opt[i][j] = opt[i+1][j+1] + 1;
                else 
                    opt[i][j] = Math.max(opt[i+1][j], opt[i][j+1]);
            }
        }

        // recover LCS itself and print it to standard output
        int i = 0, j = 0;
        int maxSize = (M > N) ? M : N;
        
        byte[] tempBytes = new byte[maxSize];
        int commonBytes = 0;
        
        while(i < M && j < N) {
            // Source and current
        	if (source[i] == current[j]) {
        		tempBytes[commonBytes++] = source[i];
                i++;
                j++;
            }
            else if (opt[i+1][j] >= opt[i][j+1]) {
            	i++;
            }
            else {
            	j++;
            }
        }
        
        byte[] byteArray = new byte[commonBytes]; 
        System.arraycopy(tempBytes, 0, byteArray, 0, commonBytes);
        return byteArray;
	}

	public static String computeLCS(String source, String current) {
		return new String(computeLCS(source.getBytes(), current.getBytes()));
	}
	
	public static void main(String[] args) {
		String source = "textpadtextpadtextpadtextpadtextpadtextpadtextpadtextpadtextpadtextpadtextpadtextpadsdfabcabcabcabcabc";
		String current = "texttextpadtextpadtextpadtextpadtextpadtextpadsdfdfdsdfdfdsdfdfdsdfdfdsdfdfdsdfdfdsdfdfdsdfdfdsdfdfdsdfdfdsdfdfdsdfdfdsdfdfdsdfdfd";
		
		long timeBefore = System.currentTimeMillis();
		byte[] byteArrayLCS = new byte[0];
		final int LIMIT = 50000;
		
		for (int i = 0; i < LIMIT; i++) {
			byteArrayLCS = computeLCS(source.getBytes(), current.getBytes());
		}
		long timeAfter = System.currentTimeMillis();
	
		long timeDifferenceInMilliseconds = timeAfter - timeBefore;
		double timeDifferenceInSeconds = (double) timeDifferenceInMilliseconds / 1000;
		System.out.println(new String(byteArrayLCS) + " took " + timeDifferenceInMilliseconds + "ms" + " " + (LIMIT/timeDifferenceInSeconds) + " LCS computations/s");
		System.exit(0);
	}
}
